"""
选择排序

计算机内存的工作原理：
    计算机就像很多抽屉的集合体，每个抽屉都有地址。

常见数组和链表操作的运行时间：
            数组      链表
    读取     O(1)     O(n)
    插入     O(n)     O(1)
    删除     O(n)     O(1)


小结：
    1.计算机内存犹如一大堆抽屉。
    2.需要存储多个元素时，可以使用数组或链表。
    3.数组的元素都在一起。
    4.链表的元素是分开的，其中每个元素都储存了下一个元素的地址。
    5.数组的读取速度很快。
    6.链表的插入和删除速度很快。
"""

import copy


def find_smallest(arr):
    """
    查找数组的最小元素的索引
    """

    # 最小元素
    smallest = arr[0]
    # 最小元素索引
    smallest_index = 0

    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i

    return smallest_index


def selection_sort(arr):
    """
    选择排序
    """

    new_arr = []

    # 拷贝原数组
    arr_ = copy.copy(arr)

    for i in range(len(arr_)):
        smallest = find_smallest(arr_)
        new_arr.append(arr_.pop(smallest))

    return new_arr


if __name__ == "__main__":
    arr = [5, 4, 8, 7, 9]

    # 选择排序
    print(selection_sort(arr))
    # 原数组
    print(arr)
